<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Bin Packing
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial060.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial062.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc126">8.8</A>&nbsp;&nbsp;Bin Packing</H2><UL>
<LI><A HREF="tutorial061.html#toc67">Problem Definition</A>
<LI><A HREF="tutorial061.html#toc68">Problem Model - Using Structures</A>
<LI><A HREF="tutorial061.html#toc69">Handling an Unknown Number of Bins</A>
<LI><A HREF="tutorial061.html#toc70">Constraints on a Single Bin</A>
<LI><A HREF="tutorial061.html#toc71">Symmetry Constraints</A>
<LI><A HREF="tutorial061.html#toc72">Search</A>
</UL>

This section presents a worked example using finite domains to solve a
bin-packing problem.<BR>
<BR>
<A NAME="toc67"></A>
<H3 CLASS="subsection"><A NAME="htoc127">8.8.1</A>&nbsp;&nbsp;Problem Definition</H3>
In this type of problem the goal is to pack a certain amount of
different items into the minimal number of bins under specific constraints.
Let us solve an example given by Andre Vellino in the Usenet
group comp.lang.prolog, June 93:
<UL CLASS="itemize"><LI CLASS="li-itemize">
There are 5 types of items:<BR>
<BR>
<EM>glass</EM>, <EM>plastic</EM>, <EM>steel</EM>, <EM>wood</EM>, <EM>copper</EM><BR>
<BR>
<LI CLASS="li-itemize">There are three types of bins:<BR>
<BR>
<EM>red</EM>, <EM>blue</EM>, <EM>green</EM><BR>
<BR>
<LI CLASS="li-itemize">The capacity constraints imposed on the bins are:
<UL CLASS="itemize"><LI CLASS="li-itemize">
red has capacity 3
<LI CLASS="li-itemize">blue has capacity 1
<LI CLASS="li-itemize">green has capacity 4
</UL><BR>
<BR>
<LI CLASS="li-itemize">The containment constraints imposed on the bins are:
<UL CLASS="itemize"><LI CLASS="li-itemize">
red can contain glass, wood, copper
<LI CLASS="li-itemize">blue can contain glass, steel, copper
<LI CLASS="li-itemize">green can contain plastic, wood, copper
</UL><BR>
<BR>
<LI CLASS="li-itemize">The requirement constraints imposed on component types (for all bin
 types) are:<BR>
<BR>
wood requires plastic<BR>
<BR>
<LI CLASS="li-itemize">Certain component types cannot coexist:
<UL CLASS="itemize"><LI CLASS="li-itemize">
glass and copper exclude each other
<LI CLASS="li-itemize">copper and plastic exclude each other
</UL><BR>
<BR>
<LI CLASS="li-itemize">The following bin types have the following capacity constraints for certain
components:
<UL CLASS="itemize"><LI CLASS="li-itemize">
red contains at most 1 wood item
<LI CLASS="li-itemize">blue implicitly contains at most 1 wood item
<LI CLASS="li-itemize">green contains at most 2 wood items
</UL><BR>
<BR>
<LI CLASS="li-itemize">Given the initial supply stated below, what is the minimum total
 number of bins required to contain the components?
<UL CLASS="itemize"><LI CLASS="li-itemize">
1 glass item
<LI CLASS="li-itemize">2 plastic items
<LI CLASS="li-itemize">1 steel item
<LI CLASS="li-itemize">3 wood items
<LI CLASS="li-itemize">2 copper items
</UL>
</UL>
<A NAME="toc68"></A>
<H3 CLASS="subsection"><A NAME="htoc128">8.8.2</A>&nbsp;&nbsp;Problem Model - Using Structures</H3>
In modelling this problem we need to refer to an array of quantities
of glass items, plastic items, steel items, wood items and copper
items. We therefore introduce:<BR>
<BR>
A structure to hold this array:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- local struct(contents(glass, plastic, steel, wood, copper)).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
A structure that defines the colour for each of the bin types:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- local struct(colour(red, blue, green)).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
By defining the bin colours as fields of a structure there is an implicit
integer value associated with each colour. This allows the readability of the code
to be preserved by writing, for example, <TT>red of colour</TT> rather than
explicitly writing the colour's integer value `<TT>1</TT>'.<BR>
<BR>
And a structure that represents the bin itself, with its colour, 
capacity and contents:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- local struct(bin(colour, capacity, contents:contents)).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> The <TT>contents</TT> attribute of <TT>bin</TT> is itself a <TT>contents</TT> structure. The <TT>contents</TT> field declaration within the <TT>bin</TT>
structure using '<TT>:</TT>' allows field names of the <TT>contents</TT>
structure to be used as if they were field names of the <TT>bin</TT>
structure. More information on accessing nested structures and 
structures with <EM>inherited</EM> fields can be found in
section&nbsp;<A HREF="tutorial024.html#structures">4.1</A> and in the <EM>Structure Notation</EM> section of 
the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> User Manual.
</DL>
</TD>
</TR></TABLE>
<BR>
The predicate <CODE>solve_bin/2</CODE> is the general predicate
that takes an amount of components packed into a <CODE>contents</CODE>
structure and returns the solution.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
?- Demand = contents{glass:1, plastic:2, steel:1, wood:3, copper:2},
   solve_bin(Demand, Bins).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<A NAME="toc69"></A>
<H3 CLASS="subsection"><A NAME="htoc129">8.8.3</A>&nbsp;&nbsp; Handling an Unknown Number of Bins</H3><BR>
<BR>
<CODE>solve_bin/2</CODE> calls <CODE>bin_setup/2</CODE> to
generate a list <I>Bins</I>.
It adds redundant constraints to remove symmetries (two
solutions are considered symmetrical if they are
the same, but with the bins in a different order).
Finally it labels all decision variables in the problem.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
solve_bin(Demand, Bins) :-
    bin_setup(Demand, Bins),
    remove_symmetry(Bins),
    bin_label(Bins).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The usual pattern for solving finite domain problems is to state
constraints on a set of variables, and then label them.
However, because the number of bins needed is not known initially, it
is awkward to model the problem with a fixed set of variables.<BR>
<BR>
One possibility is to take a fixed, large enough, number of bins
and to try to find a minimum number of non-empty bins.
However, for efficiency, we choose to solve a sequence of problems,
each one with a - larger - fixed number of bins,
until a solution is found.<BR>
<BR>
The predicate <CODE>bin_setup/2</CODE>, to generate a list of bins with appropriate
constraints, works as follows.
First it tries to match the (remaining) demand with zero,
and use no (further) bins.
If this fails, a new bin is added to the bin list;
appropriate constraints are imposed on all the new bin's
variables;
its contents are subtracted from the demand;
and the <CODE>bin_setup/2</CODE> predicate calls itself recursively:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
bin_setup(Demand,[]) :- 
        all_zeroes(Demand).
bin_setup(Demand, [Bin | Bins]) :-
        constrain_bin(Bin),
        reduce_demand(Demand, Bin, RemainingDemand),
        bin_setup(RemainingDemand, Bins).

all_zeroes( 
           contents{glass:0, plastic:0, wood:0, steel:0, copper:0}
          ).

reduce_demand( 
              contents{glass:G, plastic:P, wood:W, steel:S, copper:C},
              bin{glass:BG, plastic:BP, wood:BW, steel:BS, copper:BC},
              contents{glass:RG, plastic:RP, wood:RW, steel:RS, copper:RC} 
             ) :-
       RG #= G - BG,
       RP #= P - BP,
       RW #= W - BW,
       RS #= S - BS,
       RC #= C - BC.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<A NAME="toc70"></A>
<H3 CLASS="subsection"><A NAME="htoc130">8.8.4</A>&nbsp;&nbsp;Constraints on a Single Bin</H3>
The constraints imposed on a single bin correspond exactly to the
problem statement:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
constrain_bin(bin{colour:Col, capacity:Cap, contents:C}) :-
        colour_capacity_constraint(Col, Cap),
        capacity_constraint(Cap, C),
        contents_constraints(C),
        colour_constraints(Col, C).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

<H5 CLASS="paragraph">colour_capacity_constraint</H5> 
The colour capacity constraint relates the colour of the bin to its
capacity, we implement this using the <CODE>relates/4</CODE> predicate (defined 
in section&nbsp;<A HREF="tutorial059.html#icelement">8.6.3</A>):

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
colour_capacity_constraint(Col, Cap) :-
    relates(Col, [red of colour, blue of colour, green of colour],
            Cap, [3, 1, 4]).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

<H5 CLASS="paragraph">capacity_constraint</H5>
The capacity constraint states the following:
<UL CLASS="itemize"><LI CLASS="li-itemize">
The number of items of each kind in the bin is non-negative.
<LI CLASS="li-itemize">The sum of all the items does not exceed the capacity of the bin.
<LI CLASS="li-itemize">and the bin is non-empty (an empty bin serves no purpose)
</UL>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
capacity_constraint(Cap, contents{glass:G,
                                   plastic:P,
                                   steel:S, 
                                   wood:W,
                                   copper:C}) :-
        G #&gt;= 0, P #&gt;= 0, S #&gt;= 0, W #&gt;= 0, C #&gt;= 0,
        NumItems #= G + P + W + S + C,
        Cap #&gt;= NumItems,
        NumItems #&gt; 0.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

<H5 CLASS="paragraph">contents_constraints</H5>
The contents constraints directly enforce the restrictions on items in
the bin: wood requires paper, glass and copper exclude each other, and
copper and plastic exclude each other:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
contents_constraints(contents{glass:G, plastic:P, wood:W, copper:C}) :-
        requires(W, P),
        exclusive(G, C),
        exclusive(C, P).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
These constraints are expressed as logical combinations of constraints
on the number of items.
`requires' is expressed using implication, <CODE>=&gt;</CODE>.
`Wood requires paper' is expressed in logic as `If the number of wood
items is greater than zero, then the number of paper items
is also greater than zero':

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
requires(W,P) :-
        W #&gt; 0 =&gt; P #&gt; 0.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Exclusion is expressed using disjunction, <CODE>or</CODE>.
`X and Y are exclusive' is expressed as `Either the number of items of
kind <I>X</I> is zero, or the number of items of kind <I>Y</I> is zero':

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
exclusive(X,Y) :-
        X #= 0 or Y #= 0.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

<H5 CLASS="paragraph">colour_constraints</H5>
The colour constraint limits the number of wooden items in bins of
different colours.
Like the capacity constraint, the relation between the colour and
capacity, <I>WCap</I>, is expressed using the <CODE>relates/4</CODE> predicate.
The number of wooden items is then constrained not to exceed the capacity:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
colour_constraints(Col, contents{wood:W}) :-
    relates(Col, [red of colour, blue of colour, green of colour],
            WCap, [1, 1, 2]),
    W #=&lt; WCap.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
This model artificially introduces a capacity of blue bins for
wood items (set simply at its maximum capacity for all items).<BR>
<BR>
<A NAME="toc71"></A>
<H3 CLASS="subsection"><A NAME="htoc131">8.8.5</A>&nbsp;&nbsp;Symmetry Constraints</H3>
<A NAME="binsym"></A>
To make sure two solutions (a solution is a list of bins) are not 
just different permutations of the same bins, we impose an order 
on the list of bins:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
remove_symmetry(Bins) :-
        ( fromto(Bins, [B1, B2 | Rest], [B2 | Rest], [_Last])
        do
            lex_ord(B1, B2)
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
We order two bins by imposing lexicographic order onto lists computed
from their colour and contents, (recall that in defining the bin colours 
as fields of a structure we have encoded them as integers, which allows 
them to be ordered):

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
lex_ord(bin{colour:Col1, contents:Conts1},
        bin{colour:Col2, contents:Conts2}) :-
        % Use `=..' to extract the contents of the bin as a list
        Conts1 =.. [_ | Vars1],
        Conts2 =.. [_ | Vars2],
        lexico_le([Col1 | Vars1], [Col2 | Vars2]).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The lexicographic order is imposed using <TT>ic_global</TT>'s
<A HREF="../bips/lib/ic_global/lexico_le-2.html"><B>lexico_le/2</B></A><A NAME="@default224"></A> constraint.<BR>
<BR>
<A NAME="toc72"></A>
<H3 CLASS="subsection"><A NAME="htoc132">8.8.6</A>&nbsp;&nbsp;Search</H3>
The search is done by first choosing a colour for each bin, and then
labelling the remaining variables.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
bin_label(Bins) :-
        ( foreach(bin{colour:C} Bins) do indomain(C) ),
        term_variables(Bins, Vars),
        search(Vars, 0, first_fail, indomain, complete, []).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The remaining variables are labelled by employing the first fail heuristic
(using the <CODE>search/6</CODE> predicate of the <EM>ic</EM> library).
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">Additional information on search algorithms, heuristics and their 
use in ECL</FONT><SUP><FONT COLOR="#9832CC"><I>i</I></FONT></SUP><FONT COLOR="#9832CC">PS</FONT><SUP><FONT COLOR="#9832CC"><I>e</I></FONT></SUP><FONT COLOR="#9832CC"> can be found in section&nbsp;</FONT><A HREF="tutorial086.html#chapsearch"><FONT COLOR="#9832CC">12</FONT></A><FONT COLOR="#9832CC">.</FONT>
</DL>

<HR>
<A HREF="tutorial060.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial062.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
